﻿//常用的放在这个.h文件中
#pragma once

#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
#include<thread>
#include <mutex>
#include<algorithm>
#include<unordered_map>
#include<atomic>

using std::cout;
using std::endl;

#ifdef _WIN32
#include<Windows.h>	
#else
//linux下brk mmap
#endif 

//进行条件编译 主要是页号问题  WIN64平台支持WIN32 和 win64 所以先让64位判断
#ifdef _WIN64
typedef unsigned long long PageID;
#elif _WIN32
typedef size_t PageID;
#endif // _WIN32

//最大256kb 中心缓存桶最多208个 页缓存128个桶[从1开始到128]  页转化8kb 2^13
static const size_t Max_Bytes = 256 * 1024;
static const size_t Max_Central_Barrelnum = 208;
static const size_t Max_Page_Barrelnum = 129;
static const size_t Page_Shift = 13;

//使用Windows底层调用 脱离malloc 到堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	//这里左移13位 2^13
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

//底层调用 直接释放
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}



// 封装一下 这个使用场景较多
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理切分好 小的自由链表
class FreeList
{
public:
	//用户用完内存块进行返回 头插到自由链表
	void push(void* obj)
	{
		/**((void**)obj) = _freelist;
		_freelist = obj;*/
		NextObj(obj) = _freelist;
		_freelist = obj;
		++_size;
	}

	//这里的n是几个节点
	void pushrange(void* start, void* end, size_t n)
	{
		//这里不管你有没有 直接头插
		NextObj(end) = _freelist;
		_freelist = start;
		_size += n;
	}

	//用户拿内存 从自由链表头删
	void* pop()
	{
		void* obj = _freelist;
		_freelist = *((void**)obj);
		/*void* obj = _freelist;
		_freelist = NextObj(obj);*/
		
		--_size;
		return obj;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freelist;
		end = start;
		//进行遍历
		for (size_t i = 0; i < n - 1; ++i)
		{
			//让end往后走一步
			end = NextObj(end);
		}
		_freelist = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	//判断自由链表是否为空
	bool empty()
	{
		return _freelist == nullptr;
	}

	size_t& maxsize()
	{
		return _maxsize;
	}

	size_t Size()
	{
		return _size;
	}
	
private:
	void* _freelist = nullptr;
	size_t _maxsize = 1;//最大申请几块内存
	size_t _size = 0;//一个链表里有几个节点
};


class SizeClass
{
public:
		/*整体控制在最多10% 左右的内碎⽚浪费
		[1, 128] 8byte对齐 freelist[0, 16)   16个桶
		[128 + 1, 1024] 16byte对齐 freelist[16, 72)  72 - 16 = 56个桶
		[1024 + 1, 8 * 1024] 128byte对齐 freelist[72, 128) 128 - 72 = 56个桶
		[8 * 1024 + 1, 64 * 1024] 1024byte对齐 freelist[128, 184)  26个桶
		[64 * 1024 + 1, 256 * 1024] 8 * 1024byte对齐 freelist[184, 208)  25个桶*/

	//子函数 用来计算对齐后字节大小 参数第一个是传入字节大小 第二个是要按多少字节对齐 
	//size_t _Roundup(size_t size, size_t alignnum)
	//{
	//	//如果说没有余数 说明正好等于对齐数
	//	if (size % alignnum == 0)
	//	{
	//		return alignnum;
	//	}
	//	else
	//	{
	//		return (size / alignnum + 1) * (alignnum);
	//		//假设size=7 7/8=0 0+1=1 1*8 = 8
	//		//假设size=130 130/16=8 8+1=9 9*16=144
	//	}
	//}

	//+-*/的效率不如位运算 我们使用位运算
	static inline size_t _RoundUp(size_t size, size_t alignnum)
	{
		return ((size + alignnum - 1) & ~(alignnum - 1));
		//比较难想 通过例子理解
		//假设size=7 (7+8-1)=14 ~(7)  14&(~7)
		// 0000 0111 ->7
		// 1111 1000 ->~7  高位全为1 地位全0
		// 0000 1110 ->14  // (1-7)+7 其实就是 8肯定有 后三位组合 然后& 就只剩对齐数
		// 0000 1000 ->8
 	}



	//返回对齐后字节 7应该对齐8 1应该对齐8 像上取整
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			//封装一个函数 用来计算对齐数
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			//超出256kb 以一页对齐
			return _RoundUp(size, 1 << Page_Shift);
		}
	}

	// 进行找桶
	//size_t _Index(size_t size, size_t alignnum)
	//{
	//	//如果说size%alignnum==0证明可以整数 没有余数 8%8 = 0 下标从0开始  8/8 = 1 再减1
	//	if (size % alignnum == 0)
	//	{
	//		return size / alignnum - 1;
	//	}
	//	else
	//	{
	//		//无法整除 7 / 8 = 0
	//		return size / alignnum;
	//	}
	//}

	//位运算更加高效 第一个参数就是对齐后字节大小 第二个是对齐数的指数 8 = 2^3 第二个参数就是3
	static inline size_t _Index(size_t size, size_t align_shift)
	{
		//左移就是乘 右移就是除
		return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
		//假设 size = 5  5 + (1<<3)-1  = 12  12 >> 3
		//8 4 2 1
		//1 1 0 0
		//0 0 0 1 
		//1-1 = 0 下标为0 1号桶
	}

	//计算映射到了哪个桶
	static inline size_t Index(size_t size)
	{
		//传的数据不能大于256kb
		assert(size <= Max_Bytes);

		static int group_arr[4] = { 16,56,56,56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			//前128字节有自己的桶 对齐数是8byte 所以要-128 计算返回的是从0下标开始的第几个桶 需要加上对齐数8byte的桶
			return _Index(size - 128, 4) + group_arr[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_arr[0] + group_arr[1];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8 * 1024, 10) + group_arr[0] + group_arr[1] + group_arr[2];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64 * 1024, 13) + group_arr[0] + group_arr[1] + group_arr[2] + group_arr[3];
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	//一次从中心缓存获取多少个内存块 这里的参数是对齐后的字节数
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		//限制上下限 不能给太少 也不能给太多 [2,512]
		//小的对象上限高 大对象上限低
		int num = Max_Bytes / size;
		if (num < 2)
		{
			num = 2;
		}
		if (num > 512)
		{
			num = 512;
		}
		return num;
	}

	//一次向page cache 获取多少页 [8byte - 256KB]
	//size 是对齐后的字节
	static size_t MoveNumPage(size_t size)
	{
		//限制上限
		size_t num = NumMoveSize(size);
		size_t npage = num * size;//总共要申请多少字节
		//这里要右移是考虑 如果要的总字节小 我们就给一页 一页可能也用不完
		//如果要很大 那么就给多页
		npage >>= Page_Shift;
		if (npage == 0)
		{
			npage = 1;
		}
		return npage;
	}
};

//管理多个连续页的大块内存
struct Span
{
	PageID _pagID = 0;//大块内存块的页号
	size_t _n = 0;//页的数量

	Span* _next = nullptr;//带头双链表结构
	Span* _prev = nullptr;

	size_t _usecount = 0;//切好的小的内存块的计数 当分配给thread cache就++ 当还回来就--
	void* _freelist = nullptr;//大内存切分成小内存块 就都放到这个自由列表

	bool _isuse = false;//当前是否被使用

	size_t _objSize = 0;//一个span中一个小对象的大小
};

//带头双向列表
class SpanList
{
public:

	//进行初始化 因为是带头双向循环所以一定要进行初始化
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Start()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		//头插
		Insert(Start(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void Insert(Span* pos, Span* newspan)
	{
		assert(pos);
		assert(newspan);

		//定义一个prev 就是pos的前驱节点 方便我们写
		Span* prev = pos->_prev;
		
		prev->_next = newspan;
		newspan->_prev = prev;
		newspan->_next = pos;
		pos->_prev = newspan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);//带头节点不能删

		if (pos == _head)
		{
			int x = 1;
		}

		Span* next = pos->_next;
		Span* prev = pos->_prev;

		prev->_next = next;
		next->_prev = prev;
		//这里不直接delete 是因为还要还给下一层的page cache
	}
private:
	Span* _head;//带头

public:
	//同一个桶才进行竞争锁！
	std::mutex _mux;
};